import java.util.Arrays;

public class J101201 {
    public static class MyPriorityQueue {
        public int[] elem;
        public int usedSize = 6;

        public MyPriorityQueue() {
            elem = new int[]{5,6,2,9,3,1};
            createHeap(elem);
        }

        /**
         * 建堆的时间复杂度：
         *
         * @param array
         */
        public void createHeap(int[] array) {
            if(usedSize == 0){
                return;
            }
            for(int i = (usedSize - 2) / 2; i >= 0; i-- ) {
                shiftDown(i, usedSize);
            }
        }

        /**
         *
         * @param root 是每棵子树的根节点的下标
         * @param len  是每棵子树调整结束的结束条件
         * 向下调整的时间复杂度：O(logn)
         */
        private void shiftDown(int root,int len) {
            int child = root * 2 + 1;
            while(child < len){
                int max = elem[child];
                if(child + 1 < len && elem[child + 1] > max){
                    max = elem[child++];
                }
                if(elem[root] < max){
                    int tmp = elem[root];
                    elem[root] = max;
                    elem[child] = tmp;
                    root = child;
                    child = root * 2 + 1;
                }else{
                    break;
                }
            }
        }


        /**
         * 入队：仍然要保持是大根堆
         * @param val
         */
        public void push(int val) {
            if(isFull()){
                elem = Arrays.copyOf(elem, usedSize * 2);
            }
            elem[usedSize] = val;
            shiftUp(usedSize);
            usedSize++;
        }

        private void shiftUp(int child) {
            if(usedSize <= 1){
                return;
            }
            while(child > 0){
                if(elem[child] > elem[(child - 1) / 2]){
                    int tmp = elem[child];
                    elem[child] = elem[(child - 1) / 2];
                    elem[(child - 1) / 2] = tmp;
                    child = (child - 1) / 2;
                }else{
                    break;
                }
            }
        }

        public boolean isFull() {
            return elem.length == usedSize;
        }

        /**
         * 出队【删除】：每次删除的都是优先级高的元素
         * 仍然要保持是大根堆
         */
        public void pollHeap() {
            elem = Arrays.copyOfRange(elem, 1, usedSize--);
            shiftDown(0, usedSize);
        }

        public boolean isEmpty() {
            return usedSize == 0;
        }

        /**
         * 获取堆顶元素
         * @return
         */
        public int peekHeap() {
            return elem[0];
        }
        public void myPrint(){
            System.out.print("[");
            for (int i = 0; i < usedSize; i++){
                System.out.print(elem[i]);
                if(i != usedSize - 1){
                    System.out.print(",");
                }
            }
            System.out.println("]");
        }
    }

    public static void main(String[] args) {
        MyPriorityQueue queue = new MyPriorityQueue();
//        queue.push(1);
//        queue.push(3);
//        queue.push(2);
        queue.myPrint();
        queue.push(22);
        queue.myPrint();
        queue.pollHeap();
        queue.myPrint();
    }
}
